package codingforgreat.class14;

public class Class04_CompleteTreeNodeNumber {
    // 提交时不要提交这个类
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    // 提交如下的方法
    public static int countNodes(TreeNode head) {
        if (head == null) {
            return 0;
        }
        return bs(head, 1, mostLeftLevel(head, 1));
    }
    public static int bs(TreeNode node,int Level,int h){
        if(Level == h){
            return 1;
        }
        if (mostLeftLevel(node.right, Level + 1) == h) {
            return (1 << (h - Level)) + bs(node.right, Level + 1, h);
        } else {
            return (1 << (h - Level - 1)) + bs(node.left, Level + 1, h);
        }
    }
    public static int mostLeftLevel(TreeNode root,int level){
        while(root.left != null){
            level++;
            root = root.left;
        }
        return level - 1;
    }

}
